package com.haidechizi.sort;


import java.util.Arrays;

/**
 * 插入排序
 * <p>
 * 1.循环遍历数组中的每一个数
 * <p>
 * 2.将前i个数进行排序，没比较一轮，前i个数都是排好序的数
 * <p>
 * 时间复杂度：O(n^2)
 * <p>
 * 空间复杂度：O(1)
 */
public class InsertSort {

    public void insertSort(int[] arr) {
        int length = arr.length;
        // 循环数组中的每一个数，从第一个数开始比较（只有一个数时，认为是排好序的数组，因此从1开始）
        for (int i = 1; i < length; i++) {
            // 将当前数保存下来
            int temp = arr[i];
            // 循环比较数组的前i-1个数(当前面的数大于temp时，才需要排序)
            int j;
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                // 将前面的数放后移动
                arr[j + 1] = arr[j];
            }
            // 最后j--，因此需要将j+1
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 7, 4, 6, 5, 0, 7, 9, 4, 8, 5, 7, 5};
        new InsertSort().insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
